[BZOJ3680][JSOI2004]平衡点吊打xxx

发表于 | 分类于 ， ， | | 阅读次数:

题目描述

如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结X最终平衡于何处。

注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

输入输出格式

输入格式：

文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 )

输出格式：

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。

输入输出样例

输入样例1：

1
2
3
4
3
0 0 1
0 2 1
1 1 1

输出样例1：

1
0.577 1.000

题解

一道物理题，也可以用模拟退火来瞎搞。正解要用到计算几何内容
先设平衡点为x,y，然后对所有的点产生的力正交分解，然后算合力。
但是也可以这样想：物重一定，绳子越短，重物越低，势能越小，势能又与物重成正比，所以，只要使得$\displaystyle \sum_{i=1}^n dis[i]\times weight[i]$也就是总的重力势能最小，就可以使系统平衡

这道题目的退火模型很典型，有些地方别的退火题目可能都用不到，模拟退火的细节看注释。
值得注意的是，$\displaystyle e^{-\frac{\Delta}{t}}$是一个退火公式，不一定是必须的，但是模拟退火里面用上它能更高效一点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
using namespace std;
struct Node{//点
    int x,y,weight;
}node[10005];
int n;
double ans_x,ans_y;
double ans=1e18+7,t;
const double delta=0.993;//退火常数Δ，用来控制退火速率

double E(double nowx,double nowy){//计算总的重力势能
    double sum=0;
    for(int i=1;i<=n;i++){
        double delx=nowx-node[i].x;
        double dely=nowy-node[i].y;
        sum+=(sqrt(delx*delx+dely*dely))*node[i].weight;
    }
    return sum;
}

void SA(){
    double xx=ans_x;
    double yy=ans_y;
    double t=56;//初始温度（上界）
    while(t>1e-14){//结束温度（下界）
        double tmp_x=ans_x+(rand()*2-RAND_MAX)*t;//根据温度来控制随机偏移的范围
        double tmp_y=ans_y+(rand()*2-RAND_MAX)*t;
        double new_ans=E(tmp_x,tmp_y);
        double DE=new_ans-ans;
        if(DE<0){//新的解更优，接受
            xx=tmp_x;
            yy=tmp_y;
            ans_x=xx;
            ans_y=yy;
            ans=new_ans;
        }
        else if(exp(-DE/t)*RAND_MAX>rand()){//新的解不是更优的，我们有几率接受它
            xx=tmp_x;
            yy=tmp_y;
        }
        t*=delta;
    }
}

int main(){
    srand(20011112);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>node[i].x;
        cin>>node[i].y;
        cin>>node[i].weight;
    }
    SA();
    //SA();（BZOJ只能退1-2次，多了会超时）
    //SA();
    printf("%.3lf %.3lf\n",ans_x,ans_y);
    return 0;
}

补充

关于上面提到的退火公式有一个有趣的现象，当Δ>0时（具体来说是=5），我们的不是更优的，这个函数的图像是这样的（渐进1）：

而当Δ=0时，函数恒为1
Δ<0时（具体来说是=-5），解更优，它的函数图像是这样的（渐进1）：

Δ的变化动图：

而1对于上面的程序是一个分界点，我们可以总结出规律来：

  1. 当解不是更优时，当温度越高时我们有更大的几率接受这个解，反之
  2. 当解是更优时，我们一定接受它